package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: 恢复二叉树 https://leetcode-cn.com/problems/recover-binary-search-tree/submissions/
 * @author: STU756
 * @create: 2020-09-02 11:03
 */
public class Pro0099 {
    TreeNode t1, t2, pre;
    public void recoverTree(TreeNode root) {
        inorderTraverse(root);
        if(t1 != null && t2!=null) {
            int tmp = t1.val;
            t1.val = t2.val;
            t2.val = tmp;
        }
    }
    private void inorderTraverse(TreeNode root) {
        if(root!=null) {
            inorderTraverse(root.left);
            if(pre != null && pre.val > root.val) {
                if(t1 == null) {
                    t1 = pre;
                }
                t2 = root;
            }
            pre = root;
            inorderTraverse(root.right);
        }
    }
}
